package com.yoshino.leetcode.oneHundred.eighth;

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] dp = new int[100];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }

    public int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        // 跳到 n 的方法 = n - 1 的方法数 + n - 2 的方法数
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }

    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int min = prices[0], res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (min < prices[i]) {
                res = Math.max(res, prices[i] - min);
            } else {
                min = prices[i];
            }
        }
        return res;
    }
}